package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;
import java.util.Map;

/**
 * @author ：zsy
 * @date ：Created 2022/11/3 3:18 PM
 * @description：
 */
public class 最大重复子字符串 {
    @Test
    public void test() {
        System.out.println(new Solution().maxRepeating("aaabaaaabaaabaaaabaaaabaaaabaaaaba", "aaaba"));
    }

    /**
     * "ababc", word = "ab"
     *   a b c a b c
     * a 1     1
     * b   2     2
     */
    /*class Solution {
        public int maxRepeating(String sequence, String word) {
            int ans = 0;
            int len = sequence.length();
            int wordLen = word.length();
            int[] prev = new int[len];
            int[] cur = new int[len];
            for (int i = 0; i < wordLen; i++) {
                for (int j = 0; j < len; j++) {
                    if (word.charAt(i) == sequence.charAt(j)) {
                        cur[j] = j == 0 ? 1 : prev[j - 1] + 1;
                    }
                }
                prev = Arrays.copyOf(cur, len);
                cur = new int[len];
            }
            // 寻找最长重复的子字符串
            int i = 0;
            int curLen = 0;
            while (i < len) {
                int j = i;
                while (j < len && prev[j] == wordLen) {
                    curLen++;
                    j += wordLen;
                }
                ans = Math.max(ans, curLen);
                curLen = 0;
                i = i == j ? i + 1 : j - wordLen + 1;
            }
            return ans;
        }
    }*/

    class Solution {
        public int maxRepeating(String sequence, String word) {
            int ans = 0;
            int wordLen = word.length();
            StringBuilder builder = new StringBuilder(sequence);
            int i = builder.indexOf(word);
            while (i != -1) {
                int curLen = 1;
                builder = new StringBuilder(builder.substring(i + wordLen));
                StringBuilder prev = new StringBuilder(builder);
                while (builder.indexOf(word) == 0) {
                    prev = new StringBuilder(builder.substring(1));
                    builder = new StringBuilder(builder.substring(wordLen));
                    curLen++;
                }
                builder = prev;
                i = builder.indexOf(word);
                ans = Math.max(ans, curLen);
            }
            return ans;
        }
    }
}
